#include <iterator>
#include <memory>
#include <iostream>
#include <new>
#include <utility>
#include "allocator/alloc.h"
#include "allocator/construct.h"

using __rb_tree_color_type = bool;
const __rb_tree_color_type __rb_tree_red = false;
const __rb_tree_color_type __rb_tree_black = true;

struct __rb_tree_node_base
{
    using color_type = __rb_tree_color_type;
    using base_ptr = __rb_tree_node_base *;

    color_type color; // 节点颜色，非红即黑
    base_ptr parent;  // 便于操作，保存了父节点
    base_ptr left;    // 指向左节点
    base_ptr right;   // 指向右节点

    static base_ptr minimum(base_ptr x)
    {
        while (x->left != nullptr)
            x = x->left;
        return x;
    }

    static base_ptr maximum(base_ptr x)
    {
        while (x->right != nullptr)
            x = x->right;
        return x;
    }
};

// link_type : 指向一个节点的指针
// link_type : Value, Parent指针, Left指针, Right指针
template <typename Value>
struct __rb_tree_node : public __rb_tree_node_base
{
    using link_type = __rb_tree_node<Value> *;
    Value value_field;
};

struct __rb_tree_base_iterator
{
    // 基迭代器 ： 指向一个基指针
    using base_ptr = __rb_tree_node_base::base_ptr;
    using iterator_category = std::bidirectional_iterator_tag;
    using difference_type = std::ptrdiff_t;

    // Iterator point to a node in rb-tree
    base_ptr node;

    void increment()
    {
        // 右子树非空，那么就是右子树最左下的结点
        if (node->right != nullptr)
        {
            node = node->right;
            while (node->left != nullptr)
                node = node->left;
        }
        // 右子树为空，是父亲的左孩子：那么下个结点就是父亲，是父亲的右孩子，不断往上找
        else
        {
            base_ptr y = node->parent;
            // 当前Node是一个右孩子，那么就不断往上走，直到不是父亲y的右孩子为止
            while (node == y->right)
            {
                node = y;
                y = y->parent;
            }
            // 是父亲的左孩子，那么下个结点就是父亲
            // 这里的判断是为了一种特殊情况
            if (node->right != y)
                node = y;
        }
    }

    void decrement()
    {
        // 整颗树中仅有唯一一个结点的情况
        if (node->color == __rb_tree_red && node->parent->parent == node)
            node = node->right;
        // 左子树非空的情况：那么就是左子树最右下的结点
        else if (node->left != nullptr)
        {
            base_ptr y = node->left;
            while (y->right != nullptr)
                y = y->right;
            node = y;
        }
        // 左子树为空了，那么一直交替往上走，直到当前node不是父亲的左孩子，此时父亲便是答案
        else
        {
            base_ptr y = node->parent;
            while (node == y->left)
            {
                node = y;
                y = y->parent;
            }
            node = y;
        }
    }
};

template <typename Value, typename Ref, typename Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
    using value_type = Value;
    using reference = Ref;
    using pointer = Ptr;
    using iterator = __rb_tree_iterator<Value, Value &, Value *>;
    using const_iterator = __rb_tree_iterator<Value, const Value &, const Value *>;
    using self = __rb_tree_iterator<Value, Ref, Ptr>;
    using link_type = __rb_tree_node<Value> *;

    __rb_tree_iterator() = default;
    // link_type 是 __rb_tree_node<Value>* 类型
    // node 是 __rb_tree_node_base* 类型

    // 这里不能用__rb_tree_iterator(link_type x) : node(x) {}
    // 因为这里会先调用父类构造函数构造了一个node才可以在这里的构造函数里赋值
    __rb_tree_iterator(link_type x) { node = x; }
    __rb_tree_iterator(const iterator &it) { node = it.node; }

    reference operator*() const
    {
        // 父类指针强转为子类指针
        return link_type(node)->value_field;
    }

    pointer operator->() const
    {
        return &(operator*());
    }

    self &operator++()
    {
        increment();
        return *this;
    }

    self operator++(int)
    {
        self tmp = *this;
        increment();
        return tmp;
    }

    self &operator--()
    {
        decrement();
        return *this;
    }

    self operator--(int)
    {
        self tmp = *this;
        decrement();
        return tmp;
    }

    bool operator!=(const __rb_tree_iterator &iter2) const
    {
        return this->node != iter2.node;
    }

    bool operator==(const __rb_tree_iterator &iter2) const
    {
        return this->node == iter2.node;
    }
};

// -------------- Inline Function ------------------
inline void __rb_tree_rotate_left(
    __rb_tree_node_base *x,
    __rb_tree_node_base *&root)
{
    __rb_tree_node_base *y = x->right;
    x->right = y->left;
    if (y->left != nullptr)
        y->left->parent = x;
    y->parent = x->parent;

    if (x == root)
        root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
};

inline void __rb_tree_rotate_right(
    __rb_tree_node_base *x,
    __rb_tree_node_base *&root)
{
    __rb_tree_node_base *y = x->left;
    x->left = y->right;
    if (y->right != nullptr)
        y->right->parent = x;
    y->parent = x->parent;

    if (x == root)
        root = y;
    else if (x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;
    y->right = x;
    x->parent = y;
}

template <typename Key, typename Value, typename KeyOfValue, typename Compare,
          typename Alloc = alloc>
class rb_tree
{
protected:
    using void_pointer = void *;
    using base_ptr = __rb_tree_node_base *;
    using rb_tree_node = __rb_tree_node<Value>;
    // 使用一个统一接口进行Allocator分配
    using rb_tree_node_allocator = simple_alloc<rb_tree_node, Alloc>;
    using color_type = __rb_tree_color_type;

public:
    using key_type = Key;
    using value_type = Value;
    using pointer = value_type *;
    using const_pointer = const value_type *;
    using reference = value_type &;
    using const_reference = const value_type &;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using link_type = __rb_tree_node<Value> *;

protected:
    link_type get_node()
    {
        // 调用rb_tree_node_allocator::allocate()分配一个node返回一个地址转为一个指针
        return rb_tree_node_allocator::allocate();
    }

    void put_node(link_type p)
    {
        return rb_tree_node_allocator::deallocate(p);
    }

    link_type create_node(const value_type &value)
    {
        link_type tmp = get_node();
        try
        {
            // C++ 20
            // std::construct_at(&tmp->value_field, value);
            // ::new (static_cast<void*>(tmp)) link_type(value);
            hamster::construct(&tmp->value_field, value);
        }
        catch (const std::exception &e)
        {
            std::cout << "std::construct_at failed : " << e.what() << std::endl;
            put_node(tmp);
            tmp = nullptr;
        }
        return tmp;
    }

    link_type clone_node(link_type x)
    {
        link_type tmp = create_node(x->value_field);
        tmp->color = x->color;
        tmp->left = nullptr;
        tmp->right = nullptr;
        return tmp;
    }

    void destroy_node(link_type p)
    {
        // std::destroy_at(&p->value_field);
        hamster::destroy(&p->value_field);
        put_node(p);
    }

protected:
    // node-count : 用于记录树的大小
    size_type node_count;
    link_type header;
    Compare key_compare; // function object

    // 方便取得header成员
    link_type &root() const
    {
        // header -> parent = root
        return (link_type &)(header->parent);
        // static_cast 会生成一个临时的指针右值，不能绑定到link_type&左值引用上
    }
    link_type &leftmost() const
    {
        return (link_type &)(header->left);
    }
    link_type &rightmost() const
    {
        return (link_type &)(header->right);
    }

    // 取得结点X的成员
    static link_type &left(link_type x)
    {
        return (link_type &)x->left;
    }
    static link_type &right(link_type x)
    {
        return (link_type &)x->right;
    }
    static link_type &parent(link_type x)
    {
        return (link_type &)x->parent;
    }
    static reference value(link_type x)
    {
        return x->value_field;
    }
    static const Key &key(link_type x)
    {
        // 调用KeyOfValue的operator()参数为value(x)
        return KeyOfValue()(value(x));
    }
    static color_type &color(link_type x)
    {
        return x->color;
    }
    static link_type &left(base_ptr x)
    {
        return (link_type &)x->left;
    }
    static link_type &right(base_ptr x)
    {
        return (link_type &)x->right;
    }
    static link_type &parent(base_ptr x)
    {
        return (link_type &)x->parent;
    }
    static reference value(base_ptr x)
    {
        return link_type(x)->value_field;
        ;
    }
    static const Key &key(base_ptr x)
    {
        // 调用KeyOfValue的operator()参数为value(x)
        return KeyOfValue()(value(link_type(x)));
    }
    static color_type &color(base_ptr x)
    {
        return link_type(x)->color;
    }

    // 求树的极大和极小值
    static link_type minimum(link_type x)
    {
        return static_cast<link_type>(
            __rb_tree_node_base::minimum(x));
    }

    static link_type maximum(link_type x)
    {
        return static_cast<link_type>(
            __rb_tree_node_base::maximum(x));
    }

public:
    using iterator = __rb_tree_iterator<Value, reference, pointer>;

private:
    iterator __insert(base_ptr x, base_ptr y, const value_type &v);
    link_type __copy(link_type x, link_type p);
    void __erase(link_type x);
    void clear();
    void init()
    {
        header = get_node();
        header->color = __rb_tree_red;
        // header->parent = nullptr;
        root() = nullptr;
        // header->left = header
        leftmost() = header;
        // header->right = header;
        rightmost() = header;
    }

public:
    // constructor
    rb_tree(
        const Compare &comp = Compare()) : node_count(0), key_compare(comp)
    {
        // set header
        init();
    }

    ~rb_tree()
    {
        // clear wait to implementation
        clear();
        put_node(header);
    }

    rb_tree<Key, Value, KeyOfValue, Compare, Alloc> &operator=(
        const rb_tree<Key, Value, KeyOfValue, Compare, Alloc> &x);

public:
    Compare key_comp() const
    {
        return key_compare;
    }

    // RB-tree 的起点为最左结点
    iterator begin()
    {
        return leftmost();
    }

    // RB树的终点为header
    iterator end()
    {
        return header;
    }

    bool empty() const
    {
        return node_count == 0;
    }

    size_type size() const
    {
        return node_count;
    }

    size_type max_size() const
    {
        return std::numeric_limits<size_type>::max() / sizeof(rb_tree_node);
    }

public:
    // 将x插入到RB-tree中，保持结点的独一无二
    std::pair<iterator, bool> insert_unique(const value_type &v);
    // 将x插入到RB-tree中，允许重复
    iterator insert_equal(const value_type &v);
    // 按Key查找一个具体节点的位置，返回一个迭代器类型
    iterator find(const Key &k);
    void __erase_node(link_type x);
    void __erase_node_rebalance(link_type x);
};

template <typename Key, typename Value, typename KeyOfValue,
          typename Compare, typename Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(
    const Value &v)
{
    link_type y = header;
    link_type x = root();
    while (x != nullptr)
    {
        y = x;
        // KeyOfValue 实例化一个取值函数，从value取出其key值
        // 这个类型一定要重载了operator()
        // key_compare是一个Funtor返回一个bool值
        // 遇到大值往左走，遇到小值等于往右走

        x = key_compare(
                KeyOfValue()(v), key(x))
                ? left(x)
                : right(x);
    }
    // x是插入点迭代器，y是x的父亲
    return __insert(x, y, value);
}

template <typename Key, typename Value, typename KeyOfValue,
          typename Compare, typename Alloc>
std::pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(
    const Value &v)
{
    link_type y = header;
    link_type x = root();
    bool comp = true;
    while (x != nullptr)
    {
        y = x;
        // comp 记录v的键值小于当前结点的键值
        comp = key_compare(
            KeyOfValue()(v), key(x));
        x = comp ? left(x) : right(x);
    }
    // 令迭代器j指向插入点之父节点y
    iterator j = iterator(y);
    // 如果离开while时候comp为真，遇大，应该插入左侧
    if (comp)
    {
        // 插入点的父节点为树的最左结点,此时直接插入，不需要检查
        if (j == begin())
            return std::pair<iterator, bool>(
                __insert(x, y, v), true);
        else
            /*
            --j 用于将迭代器 j 回退到当前父节点 y 的前驱节点。
            这个操作是为了检查待插入的键值是否与前驱节点的键值相同
            */
            --j;
    }
    // keycompare(a, b) : true -> a < b
    // 比较父亲y的键值是否要小于插入点，为真则插入右边
    if (key_compare(key(j.node), KeyOfValue()(v)))
        return std::pair<iterator, bool>(
            __insert(x, y, v), true);
    // 大于和小于情况都比较结束了，只有一种可能就是等于
    return std::pair<iterator, bool>(j, false);
}

template <typename Key, typename Value, typename KeyOfValue,
          typename Compare, typename Alloc>
          template<typename InputIterator>
void
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(
    const Value &v)

template <typename Key, typename Value, typename KeyOfValue,
          typename Compare, typename Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__insert(
    base_ptr x_, base_ptr y_, const Value &v)
{
    // X_ 为新插入点， y_ 为插入点的父节点，v为新
    link_type x = link_type(x_);
    link_type y = link_type(y_);
    link_type z;

    // 如果树中没有结点，或者是插在左边的情况
    if (y == header || x != nullptr ||
        key_compare(KeyOfValue()(v), key(y)))
    {
        z = create_node(v);
        left(y) = z;
        if (y == header)
        {
            root() = z;
            rightmost() = z;
        }
        else if (y == leftmost())
            leftmost() = z;
        // 1 . 情况一 ： y == header : z作为新节点插入，分别执行了 : z = create_node(v) ; left(y) = z; root() = z; rightmost() = z
        // 2 . 情况二 ： y == leftmost() : 是中序遍历最前之前插入，分别执行了 : z=create_node(v);left(y)=z;leftmost()=z
    }
    else
    {
        // 插在右边的情况
        z = create_node(v);
        right(y) = z;
        if (y == rightmost())
            rightmost() = z;
        // y == header 情况已经在上面处理过了
        // 只有y == rightmost() 情况了
    }
    // 在这里统一设置z的指针
    parent(z) = y;
    left(z) = nullptr;
    right(z) = nullptr;

    // 重新把树调整平衡
    __rb_tree_rebalance(z, header->parent);
    ++node_count;
    return iterator(z);
}

// param 1 : insert node
// param 2 : root node
// 这里把LL和LR合一起，RL和RR合一起。LR多一步左旋，RL多一步右旋
inline void __rb_tree_rebalance(
    __rb_tree_node_base *x,
    __rb_tree_node_base *&root)
{
    // 只可能会被破坏了两个相同的红节点这个规则
    // 新插入结点为红色
    x->color = __rb_tree_red;
    // 当前插入结点的父节点也是红色
    while (x != root && x->parent->color == __rb_tree_red)
    {
        // 父结点为爷结点的左孩子
        if (x->parent == x->parent->parent->left)
        {
            // y 为叔叔结点
            __rb_tree_node_base *y = x->parent->parent->right;
            // 红叔叔
            if (y && y->color == __rb_tree_red)
            {
                // 叔父爷同时变色，爷爷结点变为新节点以递归调整
                x->parent->color == __rb_tree_black;
                y->color = __rb_tree_black;
                // 自己为红，父亲为黑叔叔为黑，爷爷只能是红
                x->parent->parent->color = __rb_tree_red;
                // 递归调整 : 爷变新
                x = x->parent->parent;
            }
            // 没有叔叔结点（即叔叔是黑的），或者是有叔叔，叔叔是黑的
            else
            {
                if (x == x->parent->right)
                {
                    // 即黑叔叔。并且是LR型不平衡：左右双旋，儿子换爷爷，两者变色
                    x = x->parent;
                    // 左旋点为插入点的父亲，即x->parent, 第二参数为根
                    __rb_tree_rotate_left(x, root);
                }
                // 上面的__rb_tree_rotate_left(x, root)执行后，x应该还是指向了新节点x
                // 无论是x == x->parent->right还是x == x->parent->left都要执行
                x->parent->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                __rb_tree_rotate_right(x->parent->parent, root);
            }
        }
        //  父结点为爷结点的右孩子
        else
        {
            // 叔叔
            __rb_tree_node_base *y = x->parent->parent->left;
            if (y && y->color == __rb_tree_red)
            {
                // 红叔叔
                // 叔父爷染色，爷变新
                x->parent->color = __rb_tree_black;
                y->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                x = x->parent->parent;
            }
            else
            {
                if (x == x->parent->left)
                {
                    x = x->parent;
                    __rb_tree_rotate_right(x, root);
                }
                x->parent->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                __rb_tree_rotate_left(x->parent->parent, root);
            }
        }
    }
    // 根节点永远为黑色
    root->color = __rb_tree_black;
}

template <typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::clear()
{
    __erase(root());
    left(header) = header;
    right(header) = header;
    parent(header) = nullptr;
}

template <typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__erase(link_type x)
{
    if (x == nullptr)
        return;
    __erase(left(x));
    __erase(right(x));
    destroy_node(x);
}

template <typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc>
auto rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key &k)
    -> rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
{
    link_type y = header;
    link_type x = root();

    while (x != nullptr)
    {
        if (!key_compare(key(x), k))
            y = x, x = left(x);
        else
            x = right(x);
    }

    iterator j = iterator(y);
    return (j == end() || key_compare(k, key(j.node))) ? end() : j;
}

template <typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__erase_node(link_type x)
{
    // 删叶子
    if (x->left == nullptr && x->right == nullptr)
    {
        // 删除的叶子是红的，直接删除
        if (x->color == __rb_tree_red)
        {
            if (leftmost() == x)
                leftmost() = (link_type)x->parent;
            else if (rightmost() == x)
                rightmost() = (link_type)x->parent;
        }
        // 删除叶子是黑色的，最麻烦
        else
        {
            if (root() == x)
            {
                root() == nullptr;
                leftmost() == header;
                rightmost() == header;
            }
            else
            {
                // 此处x一定有兄弟节点
                // 调用处理函数
                __erase_node_rebalance(x);

                if (leftmost() == x)
                    leftmost() = (link_type)x->parent;
                if (rightmost() == x)
                    rightmost() = (link_type)x->parent;
            }
        }

        if (x->parent->left == x)
            x->parent->left = nullptr;
        else
            x->parent->right = nullptr;
        destroy_node(x);
        --node_count;
    }
    else if (x->left == nullptr)
    {
        // 被删除节点只有一个子节点，那么被删节点一定是黑的，不可能是红的
        // 被删node的另一个子节点必然是红色的，把node删除后，用value代替node位置，把value着黑即可
        link_type son = (link_type)x->right;
        son->parent = x->parent;
        son->color = __rb_tree_black;

        if (x->parent->left == x)
            x->parent->left = son;
        else
            x->parent->right = son;

        if (root() == x)
            root() = son;
        // 只可能是最左下中序遍历的第一个节点而不可能是最后一个
        if (leftmost() == x)
            leftmost() = son;

        destroy_node(x);
        --node_count;
    }
    else if (x->right == nullptr)
    {
        link_type son = (link_type)x->right;
        son->parent = x->parent;
        son->color = __rb_tree_black;

        if (x->parent->left == x)
            x->parent->left = son;
        else
            x->parent->right = son;

        if (root() == x)
            root() = son;
        // 只可能是最右下中序遍历的最后一个节点
        if (rightmost() == x)
            rightmost() = son;

        destroy_node(x);
        --node_count;
    }
    // 被删节点有两个孩子的情况
    else
    {
        iterator it = iterator(x);
        // 中序后裔元素代替当前节点，转为递归删后裔
        ++it;
        static_cast<link_type>(x)->value_field = *it;

        __erase_node((link_type)it.node);
    }
}

// 被删节点x为叶子且为黑色的平衡操作
template <typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__erase_node_rebalance(link_type x)
{
    link_type brother;
    if(x == x->parent->left) brother = (link_type)x->parent->right;
    else                     brother = (link_type)x->parent->left;

    // brother为黑色，情形一二三
    if(brother->color == __rb_tree_black)
    {
        // 情形一和二
        if(
            (brother->left && brother->left->color == __rb_tree_red) ||
            (brother->right && brother->right->color == __rb_tree_red)
        )
        {
            if(brother == x->parent->right)
            {
                // 情况一：
                // brother为黑色, brother为右孩子，且brother有一个右孩子为红色
                // parent和brother左旋并重新着色
                if(brother->right != nullptr)
                {
                    __rb_tree_rotate_left(x->parent, header->parent);
                    brother->right->color = __rb_tree_black;
                    brother->color = x->parent->color;
                    x->parent->color = __rb_tree_black;
                }
                // 情况二：
                // brother为黑色，brother为右孩子，brother有一个左孩子son且为红色
                // son和brother右旋并染色后变为情况一
                else
                {
                    __rb_tree_rotate_right(brother, header->parent);
                    brother->color = __rb_tree_red;
                    brother->parent->color = __rb_tree_black;
                    __erase_node_rebalance(x);
                }
            }
            // brother == x->parent->left
            else
            {
                // 情况一：
                // brother为黑色, brother为左孩子，且brother有一个左孩子为红色
                // parent和brother右旋并重新着色
                if(brother->left != nullptr)
                {
                    __rb_tree_rotate_right(x->parent, header->parent);
                    brother->left->color = __rb_tree_black;
                    brother->color = x->parent->color;
                    x->parent->color = __rb_tree_black;
                }
                // 情况二：
                // brother为黑色，brother为左孩子，brother有一个右孩子son且为红色
                // son和brother左旋并染色后变为上面的情况一
                else
                {
                    __rb_tree_rotate_left(brother, header->parent);
                    brother->color = __rb_tree_red;
                    brother->parent->color = __rb_tree_black;
                    __erase_node_rebalance(x);
                }
            }
        }
        // 情形三
        else
        {
            // 递归结束回溯到根了
            if(x == root()) return;
            
            // 情形3.1
            // brother为黑色，且brother没有红色子节点，且parent为红色，那么重新把father和parent染色即可
            if(x->parent->color == __rb_tree_red)
            {
                x->parent->color = __rb_tree_black;
                brother->color = __rb_tree_red;
            }
            // 情形3.2
            // brother为黑色，且brother没有红色子节点，且parent为黑色
            // 将brother重新着色，把father作为双权重黑色节点(自身黑和brother的黑合并)进行判断，遇到情形一和二则递归上溯判断
            // 直到根存储额外的黑色则结束
            else
            {
                brother->color = __rb_tree_red;
                // 回到情形一和二继续判断
                // 对parent递归这个过程（这时parent在算法思想上黑色权重为2）
                // 以上将brother子树的黑节点减少一层，将x的黑色权重2（只是在算法思路上存在）移一个到father，
				// 递归这个过程，直至遇到其他情形解决问题或递归到根节点
                __erase_node_rebalance((link_type)x->parent);
            }
        }
    }
    // brother为红色
    // 情形四
    // 因为brother为红色，那么parent一定是黑色(不红红)
    // 将brother和father旋转，重新上色后，被删节点的新的brother（原来的son）变成了黑色，这样就成了情形一、二、三中的一种
    // https://blog.csdn.net/qq_40843865/article/details/102498310
    else
    {
        if(brother == x->parent->right)
        {
            __rb_tree_rotate_left(x->parent, header->parent);
        }
        else
        {
            __rb_tree_rotate_right(x->parent, header->parent);
        }

        brother->color = __rb_tree_black;
        x->parent->color = __rb_tree_red;

        // 回溯到情况一二三处理
        __erase_node_rebalance(x);

    }
}